#include <iostream>
#include <vector>
using namespace std;

/*
                opt(m, n - 1)
opt(m, n) =
                opt(m - w[i], n) + c[i]
*/

int max_cost_recur(vector<int> &w, vector<int> &c, int m, int n)
{
        if(n == 0){
                return 0;
        }

        int max_cost = max_cost_recur(w, c, m, n - 1);
        if(m >= w[n]){
                max_cost = max(max_cost, max_cost_recur(w, c, m - w[n], n) + c[n]);
        }

        return max_cost;
}

int max_cost_recur(vector<int> &w, vector<int> &c, int m, int n, vector<vector<int>> &recd)
{
        if(n == 0){
                return recd[n][m] = 0;
        }

        if(recd[n][m] != -1){
                return recd[n][m];
        }

        int max_cost = max_cost_recur(w, c, m, n - 1, recd);
        if(m >= w[n]){
                max_cost = max(max_cost, max_cost_recur(w, c, m - w[n], n, recd) + c[n]);
        }

        return recd[n][m] = max_cost;
}

int max_cost_dp(vector<int> &w, vector<int> &c, int m, int n)
{
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        dp[i][j] = dp[i - 1][j];
                        if(j >= w[i]){
                                dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + c[i]);
                        }
                }
        }
        return dp.back().back();
}

int max_cost_dp_sp(vector<int> &w, vector<int> &c, int m, int n)
{
        vector<int> dp(m + 1, 0);
        for(int i = 1; i <= n; i++){
                for(int j = w[i]; j <= m; j++){
                        dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
                }
        }
        return dp.back();
}

int main()
{
        int m, n;
        cin>>m>>n;
        vector<int> c(n + 1, 0), w(n + 1, 0);
        for(int i = 1; i <= n; i++){
                cin>>w[i]>>c[i];
        }

        vector<vector<int>> recd(n + 1, vector<int>(m + 1, -1));

        cout<<"max="<<max_cost_dp_sp(w, c, m, n)<<endl;
        return 0;
}